package com.ttx.algorithm.leetcode.doublepoint;

import cn.hutool.core.lang.Assert;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
 *
 * 看图 p42rainwatertrap.png
 *
 * 示例:
 *
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author TimFruit
 * @date 20-4-26 上午11:29
 */
public class P42TrappingRainWater {
    public static void main(String[] args) {
        int[] array=new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
//        int[] array=new int[]{0,1,0,2,1,0,1,3};
        int expectResult=6;

        Solution solution=new Solution();

        int re=solution.trap(array);
        System.out.println(re);
        Assert.state(re==expectResult);

    }



}
class Solution {
    public int trap(int[] height) {
        if(height==null || height.length<=2){
            return 0;
        }

        int total=0;
        int left=0;

        //左低右高
        for(int i=0;i<height.length;i++){
            if(height[left]<=height[i]){//计算赋值

                if(left+2<=i && height[left]>height[left+1] && height[i]>height[i-1]){
                    int tmpTotal=0;
                    for(int j=left+1;j<i;j++){
                        tmpTotal+=height[j];
                    }

                    total=total+(height[left]*(i-left-1) - tmpTotal);
                }

                left=i;
            }
        }


        //左高右低
        int right=height.length-1;
        for(int i=right;i>=left;i--){
            if(height[right]<=height[i]){//计算赋值
                if(i+2<=right && height[i]>height[i+1] && height[right]>height[right-1]){
                    int tmpTotal=0;
                    for(int j=i+1;j<right;j++){
                        tmpTotal+=height[j];
                    }

                    total=total+(height[right]*(right-i-1) - tmpTotal);
                }

                right=i;
            }


        }



        return total;
    }
}